COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Summary of the Benchmarks
C00012 ENDMK
C⊗;
Summary of the Benchmarks

TAK

TAK is a simple, doubly-recursive benchmark, which simply exercises
function-call and fixed point arithmetic.
When called as (tak 18 12 6), TAK makes 63,609 function calls and
performs 47,706 subtractions by 1. The result of the function is 7.
The depth of recursion is never greater than 18. No garbage collection
takes place in the MacLisp version of this function because small
fixnums are used.

STAK

STAK is a variant of TAK; it uses special binding to pass arguments
rather than the normal argument-passing mechanism. 

CTAK

CTAK is a variant of TAK which uses CATCH and THROW to return values
rather than the function-return mechanism. Not all Lisps have CATCH/THROW
functionality, and InterLisp can mimic the behavior of CATCH/THROW with
its much more powerful spaghetti stack. The times for InterLisp on this
benchmark are quite slow, but the mimicking requires twice the number of
function calls!

TAKL

TAK measures some amount of numeric operations---1-. 47,706 such subtractions
by 1 are done. To separate out this computation, and to make this benchmark more
of a purely symbol-manipulating program, Larry Masinter suggested that we use
a unary representation of numbers instead of the usual machine representations.
In TAKL, N is represented by the list (n,n-1,n-2,...,1).

The function < is implemented by SHORTERP, which tests whether one list is
shorter than the other. We use global variables, 18L, 12L, and 6L to
start off the process.

Notice that SHORTERP is defined recursively; implementations which do tail recursion
will do much better on this benchmark than implementations which don't. Because 
of the average size of the lists being compared with SHORTERP, approximately 10 times
as many calls are made to SHORTERP than to MAS itself.

TAKR

TAKR is a function that was defined to thwart the effectiveness of cache
memories. TAKR comprises 100 copies of TAK, each with a different name.
Where TAK recursively calls itself, TAKR will call a pre-determined, but random,
copy of itself. Above, TAK18 calls TAK19, TAK3, TAK9, and TAK23.

Unfortunately, the cache on many machines is large enough to keep
most of the 100 functions in the cache. For small machines, though, with a
cache, there will be a difference. 

BOYER

J Moore and Bob Boyer wrote this benchmark as quick means of guessing how
fast their theorem-proving program would run if they translated it into
some other Lisp system.  Roughly speaking, it is a rewrite rule based
simplifier combined with a very dumb tautology-checker, which has a
three-place IF as the basic logical connective.

It is a CONS-intensive program; it also uses property-lists to
store rewrite axioms.

BROWSE

This program is intended to perform many of the operations that an expert
system might perform. There is a simple pattern matcher which uses the
form of a symbol to determine its role within a pattern; and the data base
of `units' or `frames' is implemented as property lists. In some ways this
benchmark duplicates some of the operations in BOYER, but it is a little more
careful about the relative numbers of operations.

The data base of patterns is matched against a pre-determined set of data.
The data base is medium-large and is randomly searched.

DESTRUCTIVE

Destructive benchmarks the `destructive' (hence the name) list utilities.
It does this by constructing a tree, which is a list of lists,
then destructively modifying its elements.
This manipulation proceeds by means of a fairly elaborate, iterative control 
structure.  

TRAVERSE

Traverse is split into two parts: the initialization and the actual traversal.
This benchmarks tries to see what performance can be expected from the
abstract data structure system that the various Lisp's provide.

The basic idea is to build a 
directed graph of nodes and to then traverse it. The nodes contain
10 slots: one contains backpointers to parents, one contains pointers to sons,
one is a serial number (a fixed point number), one is a `mark' bit, and six are
available for random information.

The initialization phase of the benchmark is building the random
graph The traversal phase uses the mark bit to traverse the graph
as a mark-and-sweep garbage collector would.

DERIV

This is a symbolic derivative benchmark written by Vaughan Pratt.  The
algorithm is simple and intuitive, and it primarly does function-calls and
CONSing.

DDERIV

This is just like Deriv, but to find the piece of code that takes the
derivative of an operator applied to some arguments, the property list
of the operator is examined. That is, in Deriv, there is a piece of
code that knows how to take the derivative of (times x y). This piece
of code is located with a dispatch table built into the code keyed on
`times.' In Dderiv, this piece of code is located by looking on the property
list of `times.'

DIV2

This benchmark divides numbers by 2, where the number n is represented by
a list of n ()'s. The algorithm is to CONS a list with every other element
of the original removed. There are iterative and recursive implementations
of it.

FFT

This benchmark does a complex FFT on a 1k vector of floating point numbers.
It was written by Harry Barrow.

PUZZLE

This is Forest Baskett's puzzle benchmark. It packs 13 solids into a 5x5x5
cube. The solids are built of 1x1x1 cubes. This benchmark does 2-dimensional
array hacking.

TRIANG

This finds all solutions to the 15-puzzle, which is a triangle of 15 holes
and 14 pegs. Pieces are removed by jumping as in checkers, and the goal is
to remove all pegs but 1. This does a lot of 1-dimensional array hacking
and function-calls.

FPRINT

This prints a large structure to a file.

FREAD

This reads that large structure from a file.

TPRINT

This prints that large structure to the terminal or a window (10"x10", when
size specification is possible).